package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：排布二进制网格的最少交换次数
 *
 * @author 🧑 ‍wanwei
 * @since 2023-05-03 15:28
 */
public class DA1536 {

    public static void main(String[] args) {
        int[][] grid = {{0,1,1,0,0,0,0,0,0,0,0,0},{0,1,0,1,1,0,0,0,0,0,0,0},{0,1,1,1,0,0,0,0,0,0,0,0},{1,1,1,1,1,1,0,0,0,0,0,0},{1,1,1,1,0,1,1,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,0},{1,0,1,1,1,1,0,0,0,0,0,0},{1,1,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,1,1,1,0,0,0,0,0},{0,0,1,1,1,0,1,0,0,0,0,0},{1,0,0,0,0,1,1,0,0,0,0,0},{0,1,0,0,0,0,0,0,0,0,0,0}};
        PrintUtil.print(grid);
        System.out.println(minSwaps(grid));
    }


    /**
     * 从n列开始找到第一个1 将其往下移 记录步数
     * 从n-1列开始找第一个1 将其往下移 记录步数
     * ...
     *
     * 一旦存在无法满足条件的情况存在 就返回-1
     *
     * 解法部分合理  但依旧处理不了全部场景 失败!!(除非把所有情况全部走一遍 比较较小值才行)
     * @param grid
     * @return
     */
    public static int minSwaps(int[][] grid) {
        int length = grid.length;
        //实时记录当前表格行数
        int[] index = new int[grid.length];
        //赋初始值
        for (int i = 0; i < index.length; i++) {
            index[i] = i;
        }
        int num = 0;
        int y = length -1;

        while (y != 0){
            int total = 0;
            int x = 0;
            for (int i = 0; i <= y; i++) {
                int var = grid[index[i]][y];
                total+= var;
                if(var == 1){
                    x = i;
                }
            }
            //如果列中包含1的数量超过length - y 则说明不满足条件直接返回-1
            if(total > (length - y)){
                return -1;
            } else if (total > 1){
                //如果大于1就需要多次挪位置了 而且还需要重新判断前面的数据是否不被干扰
                //total等于几就至少要将其往下挪到y+几的位置 且需要判断前面的数是否不包含1 包含1也是不符合条件的
                //将x行移动到 y行
                int xx = 0;
                for (int n = x; n <= length; n++) {
                    //至少要挪到y-total的位置
                    if(n < (y+total-1)){
                        continue;
                    }
                    if(n == length){
                        //说明没有符合条件的数据
                        return -1;
                    }
                    int yy = y;
                    boolean flag = true;
                    while (yy<length){
                        if(grid[index[n]][yy] == 1){
                            flag = false;
                        }
                        yy++;
                    }
                    //如果符合条件 则跳出for 如果不符合条件 则继续往下走
                    if(flag){
                        xx = n;
                        break;
                    }
                }

                //更新index记录的行坐标
                int value = index[x];
                //将x行移动到 y行
                for (int n = x; n < xx; n++) {
                    index[n] = index[n+1];
                    num++;
                }
                index[xx] = value;
                continue;
            }else if(total == 1 && x != y){
                //更新index记录的行坐标
                int value = index[x];
                //将x行移动到 y行
                for (int n = x; n <= y - 1; n++) {
                    index[n] = index[n+1];
                    num++;
                }
                index[y] = value;
            }
            y--;
        }
        return num;
    }
}
